/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-06-21
 * Time: 22:47
 */
import java.util.*;

//https://www.nowcoder.com/practice/106f666170554379ab1974e5a601e741?tpId=13&tqId=39275&ru=/exam/oj
//减绳子（进阶）
public class Solution1 {
    static final long mod = 998244353;

    public long cutRope (long number) {
        if (number <= 3) {
            return number - 1;
        }
        if (number % 3 == 0) {
            return pow(3, number / 3);
        } else if(number % 3 == 1) {
            return fast(pow(3, number / 3 - 1), 4);
        } else {
            return fast(pow(3, number / 3), 2);
        }
    }

    //快速乘法
    public static long fast(long x, long y) {
        long res = 0;
        x %= mod;
        y %= mod;
        while (y != 0) {
            if ((y & 1) != 0) {
                res += x;
            }
            if (res >= mod) {
                res -= mod;
            }
            x <<= 1;
            y >>= 1;
            if (x >= mod) {
                x -= mod;
            }
        }
        return res;
    }

    //快速幂
    public static long pow(long x, long y) {
        long res = 1;
        while (y != 0) {
            if ((y & 1) != 0) {
                res = fast(res, x);
            }
            x = fast(x, x);
            y >>= 1;
        }
        return res;
    }
}